package com.leecode.arrAndSort;

/**
 * 第k个排列
 * <p>
 * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 */
public class KthPermutationMain {

	private static int nJieC;

	public static void main(String[] args) {
//		System.out.println((char)49);
//		System.out.println(getPermutation(4, 9));
//		System.out.println(getPermutation(3, 4));
		System.out.println(getPermutation(4, 4));
	}

	public static String getPermutation(int n, int k) {
		char[] chars = new char[n];
		for (int i = 0; i < chars.length; i++) {
			chars[i] = (char) (49 + i);
		}
		char[] recur = recur(chars, 0, k);
		return new String(recur);
	}


	public static char[] recur(char[] chars, int beginIndex, int k) {
		if (beginIndex == chars.length - 1) {
			return chars;
		}
		nJieC = getNJieC(chars.length - 1 - beginIndex);
		//要交换的index
		int swapNum = (k - 1) / nJieC;

		if (k > nJieC) {
			for (int i = swapNum; i >= 1; i--) {
				char temp = chars[beginIndex + i];
				chars[beginIndex+i] = chars[beginIndex + i-1];
				chars[beginIndex + i-1] = temp;
			}
			k -= (swapNum)*nJieC;
//			k %= nJieC;
			recur(chars, ++beginIndex, k);
		} else {
//			k %= nJieC;
			recur(chars, ++beginIndex, k);
		}
		System.out.println(chars);
		return chars;
	}

	public static int getNJieC(int n) {
		int sum = 1;
		while (n >= 2) {
			sum *= n;
			n--;
		}
		return sum;
	}

}
